P1438 无聊的数列

题目描述

维护一个数列 $a_{i}$ ，支持两种操作：

1 l r K D：给出一个长度等于 $r - l + 1$ 的等差数列，首项为 $K$ ，公差为 $D$ ，并将它对应加到 $[l, r]$ 范围中的每一个数上。即：令 $a_{l} = a_{l} + K, a_{l + 1} = a_{l + 1} + K + D \dots a_{r} = a_{r} + K + (r - l) \times D$ 。
2 p：询问序列的第 $p$ 个数的值 $a_{p}$ 。

输入格式

第一行两个整数数 $n, m$ 表示数列长度和操作个数。

第二行 $n$ 个整数，第 $i$ 个数表示 $a_{i}$ 。

接下来的 $m$ 行，每行先输入一个整数 $o p t$ 。

若 $o p t = 1$ 则再输入四个整数 $l r K D$ ；

若 $o p t = 2$ 则再输入一个整数 $p$ 。

$0 \leq n, m \leq 10^{5}, - 200 \leq a_{i}, K, D \leq 200, 1 \leq l \leq r \leq n, 1 \leq p \leq n$ 。

输出格式

对于每个询问，一行一个整数表示答案。

Solution

线段树/树状数组/差分

还是只用线段树相加的板子即可

差分

先将初始的数组差分，然后后面需要加的等差数列也差分，

等差数列差分规则是： $a [l] + = k, a [(l + 1), r] + = d, a [r + 1] - = k + (r - l) \times d$

在查询的时候直接查 $a$ 数组的前缀和即可。

#define lc u<<1
#define rc u<<1|1
int a[100010], dif[100010];
struct Tree { //线段树
    ll l, r, sum, add;
}tr[400010];

void pushup(ll u) { //上传
    tr[u].sum = tr[lc].sum + tr[rc].sum;
}
void pushdown(ll u) { //下传
    if (tr[u].add) {
        tr[lc].sum += tr[u].add * (tr[lc].r - tr[lc].l + 1);
        tr[rc].sum += tr[u].add * (tr[rc].r - tr[rc].l + 1);
        tr[lc].add += tr[u].add;
        tr[rc].add += tr[u].add;
        tr[u].add = 0;
    }
}
void build(ll u, ll l, ll r) { //建树
    tr[u] = {l,r,dif[l],0};
    if (l == r) return;
    ll m = l + r >> 1;
    build(lc, l, m);
    build(rc, m + 1, r);
    pushup(u);
}
void change(ll u, ll l, ll r, ll k) { //区修
    if (l <= tr[u].l && tr[u].r <= r) {
        tr[u].sum += (tr[u].r - tr[u].l + 1) * k;
        tr[u].add += k;
        return;
    }
    ll m = tr[u].l + tr[u].r >> 1;
    pushdown(u);
    if (l <= m) change(lc, l, r, k);
    if (r > m) change(rc, l, r, k);
    pushup(u);
}
ll query(ll u, ll l, ll r) { //区查
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
    ll m = tr[u].l + tr[u].r >> 1;
    pushdown(u);
    ll sum = 0;
    if (l <= m) sum += query(lc, l, r);
    if (r > m) sum += query(rc, l, r);
    return sum;
}
void solve() {
    int n, m;cin >> n >> m;
    for (int i = 1;i <= n;i++)cin >> a[i];
    for (int i = 1;i <= n;i++) {
        dif[i] = a[i] - a[i - 1];
    }
    build(1, 1, n);
    while (m--) {
        int op;cin >> op;
        if (op == 1) {
            int l, r, k, d;cin >> l >> r >> k >> d;
            change(1, l, l, k);
            if (l + 1 <= r)
                change(1, l + 1, r, d);
            if (r + 1 <= n)
                change(1, r + 1, r + 1, -(k + (r - l) * d));
        } else {
            int p;cin >> p;
            cout << query(1, 1, p) << '\n';
        }
    }
}